#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @Author  : 邢建辉
# @Email   : xjh_0125@sina.com
# @Time    : 2021/12/30 15:13
# @Software: PyCharm
# @File    : l2071_max_task_assign.py
from typing import List
import bisect


class Solution:
    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
        '''
        二分+贪心算法
        :param tasks:
        :param workers:
        :param pills:
        :param strength:
        :return:
        '''
        tasks = sorted(tasks)
        workers = sorted(workers)
        count_t, count_w = len(tasks), len(workers)
        max_k = min(count_t, count_w)
        min_k = 0
        while min_k <= max_k:
            k = (min_k + max_k) // 2
            if self.check(tasks, workers, pills, strength, k):
                min_k = k + 1
            else:
                max_k = k - 1
        if self.check(tasks, workers, pills, strength, k):
            return k
        return max(k - 1, 0)

    def check(self, tasks, workers, pills, strength, k):
        '''
        倒序遍历任务，此时考虑值最大的任务，要想完成任务，只有两种情况：
        1.不吃药情况下，让值最大的工人完成，最大的任务让最大的工人完成
        2.吃药情况下，让能完成任务的值最小的工人完成：（此时跟谁换都能完成其他【此时的其他任务小于当前任务】任务）
        :param tasks:
        :param workers:
        :param pills:
        :param strength:
        :param k:
        :return:
        '''
        tmp_workers = workers[len(workers) - k:]
        for i in range(k - 1, -1, -1):
            if tmp_workers[-1] >= tasks[i]:
                tmp_workers.pop()
            elif pills > 0:
                idx = bisect.bisect_left(tmp_workers, tasks[i] - strength)
                if idx >= len(tmp_workers):
                    return False
                else:
                    tmp_workers.pop(idx)
                    pills -= 1
            else:
                return False
        return True


if __name__ == '__main__':
    s = Solution()
    tasks = [5, 4]
    workers = [0, 0, 0]
    pills = 1
    strength = 5
    res = s.maxTaskAssign(tasks, workers, pills, strength)
    print(res)
